// zoj2112
// 题意：n(<=50000)个数，m(<=10000)个指令，有两种指令，
//        1.询问[l, r]区间第k小的数
//        2.修改p位置上的数为vp
//       输出所有询问。
//
// 题解：整体二分。对于修改我们只需要增加第三种类型的数据，把p位置修改前
//       的数作为值，树状数组遇到3类型符合条件就减（与之前的相消），然后
//       把修改后的值作为新值正常处理就行。
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>

long long const inf = (1ll) << 30;
int const maxn = 80007;
int n, m;

struct data
{
	int type; // 1 data, 2 query, 3 modify
	long long v;
	int l, r, k;
	int p, vp;
	int ans_id, id;
	int cur, one_query;
};

data da[maxn], part1[maxn], part2[maxn];
long long ans[maxn];
long long a[maxn];
int tree[maxn];

int lowbit(int x) { return x & -x; }

void bit_update(int id, int d)
{
	for (; id <= n; id += lowbit(id)) tree[id] += d;
}

int bit_sum(int id)
{
	int ret = 0;
	for (; id > 0; id -= lowbit(id)) ret += tree[id];
	return ret;
}

void divide_and_conquer(int head, int tail, long long l, long long r)
{
	if (head > tail) return;
	if (l == r) {
		for (int i = head; i <= tail; i++)
			if (da[i].type == 2) ans[da[i].ans_id] = l;
		return;
	}
	long long mid = (l + r) / 2;
	for (int i = head; i <= tail; i++)
		if (da[i].type == 1 && da[i].v <= mid) bit_update(da[i].id, 1);
		else if (da[i].type == 2) da[i].one_query = bit_sum(da[i].r) - bit_sum(da[i].l - 1);
		else if (da[i].type == 3 && da[i].v <= mid) bit_update(da[i].id, -1);
	for (int i = head; i <= tail; i++)
		if (da[i].type == 1 && da[i].v <= mid) bit_update(da[i].id, -1);
		else if (da[i].type == 3 && da[i].v <= mid) bit_update(da[i].id, 1);

	int tot1 = 0, tot2 = 0;
	for (int i = head; i <= tail; i++) {
		if (da[i].type == 2) {
			if (da[i].cur + da[i].one_query >= da[i].k)
				part1[++tot1] = da[i];
			else {
				da[i].cur += da[i].one_query;
				part2[++tot2] = da[i];
			}
		} else {
			if (da[i].v <= mid) part1[++tot1] = da[i];
			else part2[++tot2] = da[i];
		}
	}
	for (int i = 1; i <= tot1; i++) da[head + i - 1] = part1[i];
	for (int i = 1; i <= tot2; i++) da[head + i - 1 + tot1] = part2[i];
	divide_and_conquer(head, head + tot1 - 1, l, mid);
	divide_and_conquer(head + tot1, tail, mid + 1, r);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			da[i].type = 1;
			da[i].id = i;
			std::cin >> a[i];
			da[i].v = a[i];
		}
		int tot = 0, totq = n;
		for (int i = 1; i <= m; i++) {
			char ch; std::cin >> ch;
			if (ch == 'Q') {
				da[++totq].type = 2;
				da[totq].ans_id = tot++;
				da[totq].cur = 0;
				std::cin >> da[totq].l >> da[totq].r >> da[totq].k;
			} else {
				int p, vp;
				std::cin >> p >> vp;
				da[++totq].type = 3;
				da[totq].v = a[p];
				da[totq].id = p;

				da[++totq].type = 1;
				da[totq].v = vp;
				da[totq].id = p;
				a[p] = vp;
			}
		}
		divide_and_conquer(1, totq, 0, inf);
		for (int i = 0; i < tot; i++)
			std::cout << ans[i] << '\n';
	}
}

